#include "linearList.h"
using namespace std;
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}
//构造
sequenceList::sequenceList(const int& maxcap, const int& curnum, float seqlist[]){
    if (maxcap <= 0) {
        exit(0);
    }       
    if (curnum < 0) {
        exit(0);
    }
    if (curnum > 0 && seqlist == nullptr){
        exit(0);
    }
    maxCapcity = maxcap;
    curNumberOfItem = curnum;
    if (curnum > maxCapcity) {
        exit(0);
    }
    myList = new float[maxCapcity]; 

    for (int i = 0; i < curNumberOfItem; ++i) {
        myList[i] = seqlist[i]; 
    }    
}
//析构
sequenceList::~sequenceList(){
    delete []myList; 
}
//添加
bool sequenceList::addItem(const float& num){
    if (curNumberOfItem < maxCapcity){
        myList[curNumberOfItem] = num;
        curNumberOfItem++;
        return true;
    }
    else{
        return false;
    }
}
//插入
bool sequenceList::insertItem(const int& index,const float& num){
    if (index > curNumberOfItem || index < 0){
        return false;
    }
    else {
        for (int i = curNumberOfItem - 1;i >= index  ; i--){
            myList[i+1] = myList[i];
        }
    }
    myList[index]=num;
    curNumberOfItem++;
    return true;
}
//删除
int sequenceList::deleteItem(const float& num){
    int i = 0;
    while (i < curNumberOfItem && myList[i] != num){
        ++i;
    }
    if  (i >= curNumberOfItem){
        return -1;
    }
    for (int j = i ;j < curNumberOfItem;j++){
        myList[j] = myList[j+1];
    }
    curNumberOfItem--;
    return i;
}
//按序号查找
bool sequenceList::locate(const int& index, float& val){
    if (index >= curNumberOfItem || index < 0){
        return false;
    }
    else {
        val = myList[index];
        return true;
    }
}
//按值查找
int sequenceList::locate(const float& num){
    for (int i = 0;i < curNumberOfItem ;i++){
        if (myList[i]==num) return i;
    }
    return -1;
}
//倒序排列
void sequenceList::reverse(){
    for (int i=0;i<curNumberOfItem/2;i++){
        float j=myList[i];
        myList[i]=myList[curNumberOfItem-1-i];
        myList[curNumberOfItem-1-i]=j;
    }
}
//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}
//节点构造函数
listNode::listNode(float nodeData, listNode* succ){
    data = nodeData;
    next = succ;
}
//节点析构函数
listNode::~listNode(){}
//链表构造函数
linkList::linkList(){
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = nullptr;
    listSize = 0;
}

linkList::linkList(const int& n, float arr[]){
    if (n <= 0 || arr == nullptr){
        exit(0);
    }
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = nullptr;
    listSize = 0;
    for (int i = 0; i < n; i++) {
        tailInsertItem(arr[i]);
    }
}

linkList::~linkList() {
    while (firstNode->next != lastNode){
        listNode* p=firstNode->next;
        firstNode->next=p->next;
        delete p;
    }
    delete firstNode;
    delete lastNode;
    firstNode=nullptr;
    lastNode=nullptr;
    curNode=nullptr;
    listSize=0;
}

bool linkList::headInsertItem(const float& value) {
    listNode* newNode = new listNode(value);
    
    if (newNode == nullptr) {
        return false; 
    }
    
    newNode->next = firstNode->next;
    firstNode->next= newNode;
    
    if (lastNode == nullptr) {
        lastNode = newNode;
    }
    
    listSize++;
    return true;
}

// 尾插法
bool linkList::tailInsertItem(const float& value) {
    listNode* newNode = new listNode(value);
    
    if (newNode == nullptr) {
        return false; 
    }
    
    if (lastNode == nullptr) { 
        firstNode->next = newNode;
        lastNode = newNode;
    } else {
        lastNode->next = newNode;
        lastNode = newNode;
    }
    
    listSize++;
    return true;
}

// 在指定位置插入元素
int linkList::insertItem(const int& position, const float& value) {
    if (position < 0 || position > listSize) {
        return -1; 
    }
    
    if (position == 0) {
        return headInsertItem(value) ? position : -1;
    }

    if (position == listSize) {
        return tailInsertItem(value) ? position : -1;
    }
    
    listNode* newNode = new listNode(value);
    if (newNode == nullptr) {
        return -1;
    }
    
    listNode* current = firstNode->next;
    for (int i = 0; i < position - 1; i++) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
    listSize++;
    
    return position;
}

// 按值删除
int linkList::deleteItem(const float& value) {
    curNode = firstNode;
    int position=0;
    while (curNode != lastNode){
        if (curNode->next->data==value){
            if (curNode->next==lastNode){
                lastNode=curNode;
            }
            listNode* p=curNode->next;
            curNode->next=p->next;
            delete p;
            listSize--;
            return position;
        }
        curNode=curNode->next;
        position++;
    }
    return -1;
}

// 按位置查找
bool linkList::locate(const int& position, float& value) {
    if (position < 0 || position >= listSize || firstNode == nullptr) {
        return false;
    }
    listNode* p=firstNode;    
    for (int i=0;i<=position;i++){
        p=p->next;
    }
    value=p->data;
    return true;
}


// 按值查找位置
int linkList::locate(const float& value) {
    listNode* current = firstNode->next;
    int position = 0;

    while (current != nullptr) {
        if (current->data == value) {
            return position;
        }
        current = current->next;
        position++;
    }   
    return -1; 
}

// 升序排序
void linkList::ascendingOrder() {
    if (firstNode->next==lastNode||lastNode==nullptr){
        return;
    }
    bool swapped;
    do{
        listNode *current=firstNode->next;
        swapped=false;   
        while(current!=nullptr&&current->next!=nullptr){
            if(current->data>current->next->data){
                float tmp=current->data;
                current->data=current->next->data;
                current->next->data=tmp;
                swapped=true;
            }
            current=current->next;
        }
    }while(swapped);
         
}

// 链表反转
void linkList::reverse() {
   

    listNode* originalFirst = firstNode->next; 
    listNode* prev = nullptr;
    listNode* current = firstNode->next;

    while (current != nullptr) {
        listNode* nextNode = current->next;
        current->next = prev;
        prev = current;
        current = nextNode;
    }

    firstNode->next = prev;   
    lastNode = originalFirst; 
               
}


void merge(linkList& A, linkList& B) {
    
    A.ascendingOrder();
    B.ascendingOrder();

    linkList C;  
    listNode* pa = A.firstNode ? A.firstNode->next : nullptr;
    listNode* pb = B.firstNode ? B.firstNode->next : nullptr;

    while (pa != nullptr && pb != nullptr) {
        if (pa->data <= pb->data) {
            C.tailInsertItem(pa->data);
            pa = pa->next;
        } else {
            C.tailInsertItem(pb->data);
            pb = pb->next;
        }
    }
    while (pa != nullptr) {
        C.tailInsertItem(pa->data);
        pa = pa->next;
    }
    while (pb != nullptr) {
        C.tailInsertItem(pb->data);
        pb = pb->next;
    }

    C.reverse();

    if (A.firstNode) {
        listNode* cur = A.firstNode->next;
        while (cur != nullptr) {
            listNode* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
        A.firstNode->next = nullptr;
        A.lastNode = nullptr;
        A.listSize = 0;
    }

    if (A.firstNode == nullptr) {
        A.firstNode = new listNode(); 
    }
    A.firstNode->next = C.firstNode->next;
    A.lastNode = C.lastNode;
    A.listSize = C.listSize;

    C.firstNode->next = nullptr;
    C.lastNode = nullptr;
    C.listSize = 0;

    if (B.firstNode) {
        listNode* cur = B.firstNode->next;
        while (cur != nullptr) {
            listNode* nxt = cur->next;
            delete cur;
            cur = nxt;
        }
        B.firstNode->next = nullptr;
        B.lastNode = nullptr;
        B.listSize = 0;
    }

}
